package 牛客.树;

//import lombok.AllArgsConstructor;
//import lombok.Data;
//import lombok.NoArgsConstructor;

import java.util.Stack;

//@NoArgsConstructor
//@AllArgsConstructor
//@Data
public class BTree<T> {

    public BTreeNode<T> root;


    public boolean isEmpty(){
        if(root == null)
            return true;
        else
            return false;
    }

    public void RandomCreatTree(BTreeNode<T> node, T data){
        if(root == null)
            root = new BTreeNode<T>(data);
        else{
            if(Math.random() > 0.5){   //随机创建二叉树
                if(node.left == null)
                    node.left = new BTreeNode<T>(data);
                else
                    RandomCreatTree(node.left, data);
            }
            else{
                if(node.right == null)
                    node.right = new BTreeNode<T>(data);
                else
                    RandomCreatTree(node.right, data);
            }
        }
    }


    public void Visit(BTreeNode<T> current){
        if(current != null && current.data != null)
            System.out.print(current.data + " ");
        else
            System.out.print(" ");
    }
        /*
         * 递归法前序遍历
         */
    public void preOrder(BTreeNode<T> root){
        if(root == null)
            return ;
        Visit(root);
        preOrder(root.left);
        preOrder(root.right);
    }
    /*
     * 非递归法前序遍历
     */

    public void NPreOrder(BTreeNode<T> root){
        if(root != null) {
            Stack<BTreeNode<T>> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                BTreeNode<T> cur = stack.pop();
                Visit(cur);
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

    /*
     * 递归法中序遍历
     */
    public void inOrder(BTreeNode<T> root){
        if(root == null)
            return ;
        inOrder(root.left);
        Visit(root);
        inOrder(root.right);
    }


    /*
     * 非递归法中序遍历
     */
    public void NinOrder(BTreeNode<T> head){
        if(head != null) {
            Stack<BTreeNode<T>> stack = new Stack<>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }
                else{
                    BTreeNode<T> node = stack.pop();
                    Visit(node);
                    head = node.right;
                }
            }
        }
    }
    /*
     * 递归法后序遍历
     */
    public void postOrder(BTreeNode<T> root){
        if(root == null)
            return ;
        postOrder(root.left);
        postOrder(root.right);
        Visit(root);
    }

    /*
     * 非递归法后序遍历
     */
    public void NPostOrder(BTreeNode<T> root){
        Stack<BTreeNode<T>> stack = new Stack<>();
        BTreeNode<T> current = root;  //当前结点
        BTreeNode<T> pre = root;      //前一个被访问结点
        //若当前结点不空，则进栈，继续向左走
        while(!stack.isEmpty() || current != null){

            while(current.left != null){
                stack.push(current);
                current = current.left;
            }
            /*
             * 当前节点为空时，分两种情况：
             * 1、当前节点移动到栈顶处，然后访问栈顶元素的右节点
             * 2、当前节点移动到栈顶，但是栈顶元素没有右节点，这就需要弹出栈顶元素，再对此元素访问；
             * 然后再对新的栈顶元素进行判断即可
             */

            while(current != null && (current.right == null || current.right == pre)){
                Visit(current);
                pre = current;
                if(stack.isEmpty())
                    return;
                current = stack.pop();
            }
            stack.push(current);
            current = current.right;
        }
    }



}
